package common

import (
	"container/list"
	"math"
)

func swap(a []int, i int, j int) {
	a[i], a[j] = a[j], a[i]
}

/**
1. 交换排序
*/

// BubbleSort 1.1 冒泡排序
func BubbleSort(a []int) {
	n := len(a)
	for i := 0; i < n; i++ {
		swapped := false
		for j := 0; j < n-i-1; j++ {
			if a[j] > a[j+1] {
				swap(a, j, j+1)
				swapped = true
			}
		}
		if !swapped {
			break
		}
	}
}

// QuickSort 1.2 快速排序
func QuickSort(a []int) {
	quickSortRecursive(a, 0, len(a)-1)
}

func quickSortRecursive(a []int, l int, r int) {
	if l >= r {
		return
	}

	i, j := l, r
	p := a[i]

	for i < j {
		for a[j] > p && j > i {
			j--
		}

		if j > i {
			swap(a, i, j)
			i++
		}

		for a[i] <= p && j > i {
			i++
		}

		if j > i {
			swap(a, i, j)
			j--
		}
	}

	quickSortRecursive(a, l, i-1)
	quickSortRecursive(a, i+1, r) // NOTE position i is the pivots
}

/**
2. 插入排序
*/

// InsertSort 2.1 插入排序
func InsertSort(a []int) {
	n := len(a)
	for i := 1; i < n; i++ {
		x := a[i]
		j := i - 1
		for ; j >= 0 && a[j] >= x; j-- {
			a[j+1] = a[j]
		}
		a[j+1] = x
	}
}

// ShellSort 2.2 希尔排序
func ShellSort(a []int) {
	for dk := len(a) / 2; dk >= 1; dk /= 2 {
		shellSort(a, dk)
	}
}

func shellSort(a []int, dk int) {
	n := len(a)
	for i := dk; i < n; i += dk {
		x := a[i]
		j := i - dk
		for ; j >= 0 && a[j] >= x; j -= dk {
			a[j+dk] = a[j]
		}
		a[j+dk] = x
	}
}

/**
3. 选择排序
*/

// HeapSort 堆排序
func HeapSort(a []int) {
	n := len(a)
	for i := n; i > 0; i-- {
		buildHeap(a, i)
		swap(a, 0, i-1)
	}
}

func buildHeap(a []int, n int) {
	for i := n/2 - 1; i >= 0; i-- {
		adjustHeap(a, n, i)
		//adjustHeapRecursive(a, n, i)
	}
}

func adjustHeapRecursive(a []int, n int, s int) {
	var c int
	for c = 2*s + 1; c < n; c = 2*s + 1 {

		if c+1 < n && a[c+1] > a[c] { // 取俩孩子中较大者
			c++
		}

		if a[c] > a[s] {
			swap(a, c, s)
		}

		s = c
	}
}

func adjustHeap(a []int, n int, s int) {
	for s < n {
		c := 2*s + 1
		if c >= n {
			return
		}

		if c+1 < n && a[c+1] > a[c] {
			c += 1
		}

		if a[s] < a[c] {
			swap(a, s, c)
		}
		s = c
	}
}

/**
4. 归并排序
*/

// MergeSort 二路归并排序
func MergeSort(a []int) {
	b := make([]int, len(a))
	mergePartition(a, b, 0, len(a)-1)
}

func mergePartition(a []int, b []int, l int, r int) {
	if l >= r {
		return
	}
	m := (l + r) / 2
	mergePartition(a, b, l, m)
	mergePartition(a, b, m+1, r)

	mergeSort(a, b, l, m, r)
}

func mergeSort(a []int, b []int, l int, m int, r int) {
	var i, j, k int
	for i, j, k = l, m+1, 0; i <= m && j <= r; k += 1 {
		if a[i] <= a[j] {
			b[k] = a[i]
			i++
		} else {
			b[k] = a[j]
			j++
		}
	}

	for i <= m {
		b[k] = a[i]
		k++
		i++
	}

	for j <= r {
		b[k] = a[j]
		k++
		j++
	}

	for i, k = l, 0; i <= r; i, k = i+1, k+1 {
		a[i] = b[k]
	}
}

/**
5. 计数排序
*/

// CountSort 计数排序
func CountSort(a []int) {
	var (
		max = math.MinInt32
		min = math.MaxInt32
	)
	for _, e := range a {
		if e < min {
			min = e
		}

		if e > max {
			max = e
		}
	}

	bucketSize := max - min + 1
	buckets := make([]int, bucketSize)
	for _, e := range a {
		buckets[e-min]++
	}

	for i, j := 0, 0; i < bucketSize; i++ {
		for buckets[i] > 0 {
			a[j] = i + min
			j++
			buckets[i]--
		}
	}
}

/**
6. 桶排序
*/

// BucketSort 桶排序
func BucketSort(a []int) {
}

/**
7. 基数排序
*/

// RadixSort 基数排序
func RadixSort(a []int) {
	// 初始化buckets
	buckets := make([]*list.List, 10)
	for i := 0; i < 10; i++ {
		buckets[i] = list.New()
	}

	// 逐位比较
	maxBit := getMaxBitNum(a)
	for curBit := 1; curBit <= maxBit; curBit++ {
		// 入桶
		for _, e := range a {
			digit := getBitDigit(e, curBit)
			buckets[digit].PushBack(e)
		}

		// 出桶
		for i, k := 0, 0; i < 10; i += 1 {
			for buckets[i].Len() > 0 {
				e := buckets[i].Front()
				a[k] = e.Value.(int)
				buckets[i].Remove(e)
				k++
			}
		}
	}
}

// getBitDigit 获取数字n的第b位数字
func getBitDigit(n int, b int) int {
	digit := 0
	for curBit := 0; n > 0 && curBit < b; digit, n = n%10, n/10 {
		curBit++
	}
	return digit
}

// getBitNum 获取当前数十进制位数
func getBitNum(n int) int {
	var bitNum int
	for bitNum = 0; n > 0; n /= 10 {
		bitNum++
	}
	return bitNum
}

// getBitNum 获取当前数组中元素最大位数（十进制）
func getMaxBitNum(a []int) int {
	max := math.MinInt32
	for _, e := range a {
		if bn := getBitNum(e); bn > max {
			max = bn
		}
	}
	return max
}
